package com.lwl.leetcode;

/**
 * @author lwl
 * @Description TODO
 * @date 2025/9/12 11:08
 */
public class Code05LongestPalindrome {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("bababaaaa"));
    }

    public static String longestPalindrome(String s) {
        char[] charArray = s.toCharArray();
        String res = "";
        for (int i = 0; i < charArray.length; i++) {
            String s1 = getMaxPalindromeFromIndex(i, i, s);
            String s2 = getMaxPalindromeFromIndex(i, i + 1, s);
            if (s1.length() > res.length()) {
                res = s1;
            }
            if (s2.length() > res.length()) {
                res = s2;
            }
        }
        return res;
    }

    private static String getMaxPalindromeFromIndex(int left, int right, String s) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return left + 1 > right - 1 ? "" : s.substring(left + 1, right - 1 + 1);
    }

    public static String longestPalindrome2(String s) {
        int len = s.length();
        char[] charArray = s.toCharArray();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int start = 0;
        int end = 0;
        int max = 0;
        for (int i = 1; i < len; i++) {
            char right = charArray[i];
            for (int j = 0; j < i; j++) {
                char left = charArray[j];
                if (left == right) {
                    if (i - j + 1 == 2) {
                        dp[j][i] = true;
                    } else {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                }
                if (dp[j][i] && i - j + 1 > max) {
                    max = i - j + 1;
                    start = j;
                    end = i;
                }
            }
        }
        return s.substring(start, end + 1);
    }

    private static int process(char[] charArray, int start, int end) {
        if (start > end) {
            return 0;
        }
        if (start == end) {
            return 1;
        }
        if (charArray[start] == charArray[end]) {
            return process(charArray, start + 1, end - 1) + 2;
        }
        return process(charArray, start + 1, end - 1);
    }
}
